{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Ways to Distribute Candies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: waysToDistribute"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #计算分配糖果的不同方式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现有 <code>n</code> 颗 <strong>不同</strong> 糖果（分别标记为 <code>1</code> 到 <code>n</code> ）和 <code>k</code> 个相同的手袋。请把糖果分配到各个手袋中并保证每个手袋里至少有一颗糖果。</p>\n",
    "\n",
    "<p>不考虑手袋和糖果的摆放顺序，会有多种不同的分配方式。如果某种分配方式中其中一个手袋里的糖果与另一种分配方式中所有手袋里的糖果都不相同，则认为这两种分配方式不同。</p>\n",
    "\n",
    "<p>例如，<code>(1), (2,3)</code>&nbsp;与<code>(2), (1,3)</code>的分配方式是不同的，因为第一种分配方式中手袋(2,3)里的糖果2和3，在第二种分配方式中被分配到了手袋<code>(2)</code>和<code>(1,3)</code>&nbsp;中。</p>\n",
    "\n",
    "<p>已知整数&nbsp;<code>n</code>&nbsp;和&nbsp;<code>k</code>, 请返回分配糖果的不同方式。返回的答案如果数值太大，请取<code>10<sup>9</sup> + 7</code>的模，并返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/12/16/candies-1.png\" style=\"height: 248px; width: 600px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, k = 2\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>把糖果 3 分配到 2 个手袋中的一个，共有 3 种方式:\n",
    "(1), (2,3)\n",
    "(1,2), (3)\n",
    "(1,3), (2)\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, k = 2\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>把糖果 4 分配到 2 个手袋中的一个，共有 7 种方式:\n",
    "(1), (2,3,4)\n",
    "(1,2), (3,4)\n",
    "(1,3), (2,4)\n",
    "(1,4), (2,3)\n",
    "(1,2,3), (4)\n",
    "(1,2,4), (3)\n",
    "(1,3,4), (2)\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 20, k = 5\n",
    "<strong>输出：</strong>206085257\n",
    "<strong>解释：</strong>把 20 颗糖果分配到 5 个手袋种，共有 1881780996 种方式。1881780996 取 10<sup>9</sup> + 7的模，等于 206085257。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= n &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-ways-to-distribute-candies](https://leetcode.cn/problems/count-ways-to-distribute-candies/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-ways-to-distribute-candies](https://leetcode.cn/problems/count-ways-to-distribute-candies/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n2', '4\\n2', '20\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToDistribute(self, n: int, k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [[0] * (n + 1) for _ in range(k + 1)]\n",
    "        for i in range(1, k + 1):\n",
    "            f[i][i] = 1\n",
    "        for i in range(1, k + 1): #枚举袋子\n",
    "            for j in range(i + 1, n + 1): #枚举糖果\n",
    "                f[i][j] = (f[i-1][j-1] + f[i][j-1] * i) % MOD\n",
    "        return f[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def waysToDistribute(self, n: int, k: int) -> int:\n",
    "        dp = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, k + 1):\n",
    "                dp[i][j] = (dp[i-1][j-1] + j * dp[i-1][j]) % MOD\n",
    "                \n",
    "        return dp[n][k]\n",
    "\n",
    "# 测试代码\n",
    "sol = Solution()\n",
    "print(sol.waysToDistribute(5, 2))  # 输出应为 15\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def waysToDistribute(self, n: int, k: int) -> int:\r\n",
    "        MOD = 10 ** 9 + 7\r\n",
    "\r\n",
    "        dp = [[0 for _ in range(n + 1)] for _ in range(k + 1)]\r\n",
    "        for i in range(1, k + 1):\r\n",
    "            dp[i][i] = 1        #每个袋子放一个\r\n",
    "\r\n",
    "        for i in range(1, k + 1):       #袋子\r\n",
    "            for j in range(i + 1, n + 1):   #糖果数\r\n",
    "                #新的糖果，单独一个盒子\r\n",
    "                dp[i][j] = dp[i-1][j-1]\r\n",
    "                #新的糖果，加入其他的盒子\r\n",
    "                dp[i][j] += dp[i][j-1] * i\r\n",
    "\r\n",
    "                dp[i][j] %= MOD\r\n",
    "        \r\n",
    "        return dp[k][n]\r\n",
    "        \r\n",
    "        \r\n",
    "    def waysToDistribute2(self, n: int, k: int) -> int:\r\n",
    "        dp=[[0]*(n+1) for _ in range(k+1)]\r\n",
    "        for i in range(1,k+1):\r\n",
    "            dp[i][i]=1\r\n",
    "            for j in range(i+1,n+1):\r\n",
    "                dp[i][j]=(dp[i][j-1]*i+dp[i-1][j-1])%(10**9+7)\r\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def waysToDistribute(self, n: int, k: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        @lru_cache(None)\n",
    "        def dfs(n, k):\n",
    "            if k == 1 or n == k:\n",
    "                return 1\n",
    "            return (dfs(n - 1, k - 1) + dfs(n - 1, k) * k) % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "        ret = dfs(n, k)\n",
    "        dfs.cache_clear()\n",
    "        return ret % (10 ** 9 + 7)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
